/*
 * @lc app=leetcode.cn id=34 lang=java
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lc code=start
class Solution {
    public int[] searchRange(int[] nums, int target) {  
        if(nums == null || nums.length == 0) return new int[]{-1, -1};

        int low = 0, high = nums.length-1, mid=0;

		while(low <= high){
			mid = (low+high) >>> 1;
			if(nums[mid] < target) low = mid + 1;
			else if(nums[mid] > target) high = mid - 1;
			else break;
		}

        if(low > high) return new int[]{-1, -1};

    	int[] result = new int[2];

    	if(nums[low] <= target) 
            result[0] = BSR(nums, low, mid, target)[0];
    	if(nums[high] >= target) 
            result[1] = BSR(nums, mid, high, target)[1];
    	return result;
    }


    private int[] BSR(int[] a, int low, int high, int target){
		int mid;
		while(low <= high){
			mid = (low+high) >>> 1;
			if(a[mid] < target) 
                low = mid + 1;
			else if(a[mid] > target) 
                high = mid - 1;
			else{
				if(a[low] == a[high]) return new int[]{low, high};
				if(a[low] < target) return BSR(a, low+1, mid, target);
				if(a[high] > target) return BSR(a, mid, high-1, target);
			}
		}
		return new int[]{-1, -1};
	}
}
// @lc code=end

